<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>Leetcode 题解 - 动态规划 | Zhang Shuo'blog</title><meta name="keywords" content="Leetcode题解"><meta name="author" content="Zhang Shuo"><meta name="copyright" content="Zhang Shuo"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="Leetcode 题解 - 动态规划  Leetcode 题解 - 动态规划 斐波那契数列 1. 爬楼梯 2. 强盗抢劫 3. 强盗在环形街区抢劫 4. 信件错排 5. 母牛生产   矩阵路径 1. 矩阵的最小路径和 2. 矩阵的总路径数   数组区间 1. 数组区间和 2. 数组中等差递增子区间的个数   分割整数 1. 分割整数的最大乘积 2. 按平方数来分割整数 3. 分割整数构成字母字符串">
<meta property="og:type" content="article">
<meta property="og:title" content="Leetcode 题解 - 动态规划">
<meta property="og:url" content="https://zhang-shuo-fr.gitee.io/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/index.html">
<meta property="og:site_name" content="Zhang Shuo&#39;blog">
<meta property="og:description" content="Leetcode 题解 - 动态规划  Leetcode 题解 - 动态规划 斐波那契数列 1. 爬楼梯 2. 强盗抢劫 3. 强盗在环形街区抢劫 4. 信件错排 5. 母牛生产   矩阵路径 1. 矩阵的最小路径和 2. 矩阵的总路径数   数组区间 1. 数组区间和 2. 数组中等差递增子区间的个数   分割整数 1. 分割整数的最大乘积 2. 按平方数来分割整数 3. 分割整数构成字母字符串">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://zhang-shuo-fr.gitee.io/hexo3/img/12.jpg">
<meta property="article:published_time" content="2021-12-06T09:36:00.000Z">
<meta property="article:modified_time" content="2021-12-10T12:57:38.856Z">
<meta property="article:author" content="Zhang Shuo">
<meta property="article:tag" content="Leetcode题解">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://zhang-shuo-fr.gitee.io/hexo3/img/12.jpg"><link rel="shortcut icon" href="/hexo3/img/mao_tou_xiang.jpg"><link rel="canonical" href="https://zhang-shuo-fr.gitee.io/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//fonts.googleapis.com" crossorigin=""/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="manifest" href="/hexo3/pwa/manifest.json"/><link rel="apple-touch-icon" sizes="180x180" href="/hexo3/pwa/apple-touch-icon.png"/><link rel="icon" type="image/png" sizes="32x32" href="/hexo3/pwa/32.png"/><link rel="icon" type="image/png" sizes="16x16" href="/hexo3/pwa/16.png"/><link rel="mask-icon" href="/hexo3/pwa/safari-pinned-tab.svg" color="#5bbad5"/><link rel="stylesheet" href="/hexo3/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Titillium+Web&amp;display=swap" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/hexo3/',
  algolia: undefined,
  localSearch: {"path":"search.xml","languages":{"hits_empty":"找不到您查询的内容：${query}"}},
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"簡"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: true,
    post: true
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
    },
    fancybox: {
      js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
      css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: true,
  isanchor: true
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: 'Leetcode 题解 - 动态规划',
  isPost: true,
  isHome: false,
  isHighlightShrink: undefined,
  isToc: true,
  postUpdate: '2021-12-10 20:57:38'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const fontSizeVal = saveToLocal.get('global-font-size')
    if (fontSizeVal !== undefined) {
      document.documentElement.style.setProperty('--global-font-size', fontSizeVal + 'px')
    }
    
    const detectApple = () => {
      if (GLOBAL_CONFIG_SITE.isHome && /iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    document.addEventListener('pjax:complete', detectApple)})(window)</script><style type="text/css">#toggle-sidebar {left:100px}</style><meta name="generator" content="Hexo 5.4.0"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src= "" data-lazy-src="/hexo3/img/mao_tou_xiang.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/hexo3/archives/"><div class="headline">文章</div><div class="length-num">176</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/hexo3/tags/"><div class="headline">标签</div><div class="length-num">45</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/hexo3/categories/"><div class="headline">分类</div><div class="length-num">15</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/hexo3/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fa fa-heartbeat"></i><span> 小窝</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/hexo3/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/hexo3/Gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li><li><a class="site-page child" href="/hexo3/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/hexo3/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('/hexo3/img/12.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/hexo3/">Zhang Shuo'blog</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/hexo3/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fa fa-heartbeat"></i><span> 小窝</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/hexo3/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/hexo3/Gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li><li><a class="site-page child" href="/hexo3/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/hexo3/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">Leetcode 题解 - 动态规划</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-12-06T09:36:00.000Z" title="发表于 2021-12-06 17:36:00">2021-12-06</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-12-10T12:57:38.856Z" title="更新于 2021-12-10 20:57:38">2021-12-10</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/hexo3/categories/Leetcode%E9%A2%98%E8%A7%A3/">Leetcode题解</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">7.9k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>36分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="Leetcode 题解 - 动态规划"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="Leetcode-题解-动态规划"><a href="#Leetcode-题解-动态规划" class="headerlink" title="Leetcode 题解 - 动态规划"></a>Leetcode 题解 - 动态规划</h1><!-- GFM-TOC -->
<ul>
<li><a href="#leetcode-%E9%A2%98%E8%A7%A3---%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92">Leetcode 题解 - 动态规划</a><ul>
<li><a href="#%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97">斐波那契数列</a><ul>
<li><a href="#1-%E7%88%AC%E6%A5%BC%E6%A2%AF">1. 爬楼梯</a></li>
<li><a href="#2-%E5%BC%BA%E7%9B%97%E6%8A%A2%E5%8A%AB">2. 强盗抢劫</a></li>
<li><a href="#3-%E5%BC%BA%E7%9B%97%E5%9C%A8%E7%8E%AF%E5%BD%A2%E8%A1%97%E5%8C%BA%E6%8A%A2%E5%8A%AB">3. 强盗在环形街区抢劫</a></li>
<li><a href="#4-%E4%BF%A1%E4%BB%B6%E9%94%99%E6%8E%92">4. 信件错排</a></li>
<li><a href="#5-%E6%AF%8D%E7%89%9B%E7%94%9F%E4%BA%A7">5. 母牛生产</a></li>
</ul>
</li>
<li><a href="#%E7%9F%A9%E9%98%B5%E8%B7%AF%E5%BE%84">矩阵路径</a><ul>
<li><a href="#1-%E7%9F%A9%E9%98%B5%E7%9A%84%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E5%92%8C">1. 矩阵的最小路径和</a></li>
<li><a href="#2-%E7%9F%A9%E9%98%B5%E7%9A%84%E6%80%BB%E8%B7%AF%E5%BE%84%E6%95%B0">2. 矩阵的总路径数</a></li>
</ul>
</li>
<li><a href="#%E6%95%B0%E7%BB%84%E5%8C%BA%E9%97%B4">数组区间</a><ul>
<li><a href="#1-%E6%95%B0%E7%BB%84%E5%8C%BA%E9%97%B4%E5%92%8C">1. 数组区间和</a></li>
<li><a href="#2-%E6%95%B0%E7%BB%84%E4%B8%AD%E7%AD%89%E5%B7%AE%E9%80%92%E5%A2%9E%E5%AD%90%E5%8C%BA%E9%97%B4%E7%9A%84%E4%B8%AA%E6%95%B0">2. 数组中等差递增子区间的个数</a></li>
</ul>
</li>
<li><a href="#%E5%88%86%E5%89%B2%E6%95%B4%E6%95%B0">分割整数</a><ul>
<li><a href="#1-%E5%88%86%E5%89%B2%E6%95%B4%E6%95%B0%E7%9A%84%E6%9C%80%E5%A4%A7%E4%B9%98%E7%A7%AF">1. 分割整数的最大乘积</a></li>
<li><a href="#2-%E6%8C%89%E5%B9%B3%E6%96%B9%E6%95%B0%E6%9D%A5%E5%88%86%E5%89%B2%E6%95%B4%E6%95%B0">2. 按平方数来分割整数</a></li>
<li><a href="#3-%E5%88%86%E5%89%B2%E6%95%B4%E6%95%B0%E6%9E%84%E6%88%90%E5%AD%97%E6%AF%8D%E5%AD%97%E7%AC%A6%E4%B8%B2">3. 分割整数构成字母字符串</a></li>
</ul>
</li>
<li><a href="#%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97">最长递增子序列</a><ul>
<li><a href="#1-%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97">1. 最长递增子序列</a></li>
<li><a href="#2-%E4%B8%80%E7%BB%84%E6%95%B4%E6%95%B0%E5%AF%B9%E8%83%BD%E5%A4%9F%E6%9E%84%E6%88%90%E7%9A%84%E6%9C%80%E9%95%BF%E9%93%BE">2. 一组整数对能够构成的最长链</a></li>
<li><a href="#3-%E6%9C%80%E9%95%BF%E6%91%86%E5%8A%A8%E5%AD%90%E5%BA%8F%E5%88%97">3. 最长摆动子序列</a></li>
</ul>
</li>
<li><a href="#%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97">最长公共子序列</a><ul>
<li><a href="#1-%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97">1. 最长公共子序列</a></li>
</ul>
</li>
<li><a href="#0-1-%E8%83%8C%E5%8C%85">0-1 背包</a><ul>
<li><a href="#1-%E5%88%92%E5%88%86%E6%95%B0%E7%BB%84%E4%B8%BA%E5%92%8C%E7%9B%B8%E7%AD%89%E7%9A%84%E4%B8%A4%E9%83%A8%E5%88%86">1. 划分数组为和相等的两部分</a></li>
<li><a href="#2-%E6%94%B9%E5%8F%98%E4%B8%80%E7%BB%84%E6%95%B0%E7%9A%84%E6%AD%A3%E8%B4%9F%E5%8F%B7%E4%BD%BF%E5%BE%97%E5%AE%83%E4%BB%AC%E7%9A%84%E5%92%8C%E4%B8%BA%E4%B8%80%E7%BB%99%E5%AE%9A%E6%95%B0">2. 改变一组数的正负号使得它们的和为一给定数</a></li>
<li><a href="#3-01-%E5%AD%97%E7%AC%A6%E6%9E%84%E6%88%90%E6%9C%80%E5%A4%9A%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2">3. 01 字符构成最多的字符串</a></li>
<li><a href="#4-%E6%89%BE%E9%9B%B6%E9%92%B1%E7%9A%84%E6%9C%80%E5%B0%91%E7%A1%AC%E5%B8%81%E6%95%B0">4. 找零钱的最少硬币数</a></li>
<li><a href="#5-%E6%89%BE%E9%9B%B6%E9%92%B1%E7%9A%84%E7%A1%AC%E5%B8%81%E6%95%B0%E7%BB%84%E5%90%88">5. 找零钱的硬币数组合</a></li>
<li><a href="#6-%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%8C%89%E5%8D%95%E8%AF%8D%E5%88%97%E8%A1%A8%E5%88%86%E5%89%B2">6. 字符串按单词列表分割</a></li>
<li><a href="#7-%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C">7. 组合总和</a></li>
</ul>
</li>
<li><a href="#%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93">股票交易</a><ul>
<li><a href="#1-%E9%9C%80%E8%A6%81%E5%86%B7%E5%8D%B4%E6%9C%9F%E7%9A%84%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93">1. 需要冷却期的股票交易</a></li>
<li><a href="#2-%E9%9C%80%E8%A6%81%E4%BA%A4%E6%98%93%E8%B4%B9%E7%94%A8%E7%9A%84%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93">2. 需要交易费用的股票交易</a></li>
<li><a href="#3-%E5%8F%AA%E8%83%BD%E8%BF%9B%E8%A1%8C%E4%B8%A4%E6%AC%A1%E7%9A%84%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93">3. 只能进行两次的股票交易</a></li>
<li><a href="#4-%E5%8F%AA%E8%83%BD%E8%BF%9B%E8%A1%8C-k-%E6%AC%A1%E7%9A%84%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93">4. 只能进行 k 次的股票交易</a></li>
</ul>
</li>
<li><a href="#%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%BC%96%E8%BE%91">字符串编辑</a><ul>
<li><a href="#1-%E5%88%A0%E9%99%A4%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%AD%97%E7%AC%A6%E4%BD%BF%E5%AE%83%E4%BB%AC%E7%9B%B8%E7%AD%89">1. 删除两个字符串的字符使它们相等</a></li>
<li><a href="#2-%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB">2. 编辑距离</a></li>
<li><a href="#3-%E5%A4%8D%E5%88%B6%E7%B2%98%E8%B4%B4%E5%AD%97%E7%AC%A6">3. 复制粘贴字符</a><!-- GFM-TOC --></li>
</ul>
</li>
</ul>
</li>
</ul>
<p>递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。</p>
<h2 id="斐波那契数列"><a href="#斐波那契数列" class="headerlink" title="斐波那契数列"></a>斐波那契数列</h2><h3 id="1-爬楼梯"><a href="#1-爬楼梯" class="headerlink" title="1. 爬楼梯"></a>1. 爬楼梯</h3><p>70. Climbing Stairs (Easy)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/climbing-stairs/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/climbing-stairs/description/">力扣</a></p>
<p>题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。</p>
<p>定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。</p>
<p>第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。</p>
<!--<div align="center"><img src= "" data-lazy-src="https://latex.codecogs.com/gif.latex?dp[i]=dp[i-1]+dp[i-2]" class="mathjax-pic"/></div> <br>-->

<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/14fe1e71-8518-458f-a220-116003061a83.png" width="200px"> </div><br>

<p>考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">climbStairs</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (n &lt;= <span class="number">2</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> n;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> pre2 = <span class="number">1</span>, pre1 = <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> cur = pre1 + pre2;</span><br><span class="line">        pre2 = pre1;</span><br><span class="line">        pre1 = cur;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pre1;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-强盗抢劫"><a href="#2-强盗抢劫" class="headerlink" title="2. 强盗抢劫"></a>2. 强盗抢劫</h3><p>198. House Robber (Easy)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/house-robber/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/house-robber/description/">力扣</a></p>
<p>题目描述：抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。</p>
<p>定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。</p>
<p>由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以</p>
<!--<div align="center"><img src= "" data-lazy-src="https://latex.codecogs.com/gif.latex?dp[i]=max(dp[i-2]+nums[i],dp[i-1])" class="mathjax-pic"/></div> <br>-->

<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/2de794ca-aa7b-48f3-a556-a0e2708cb976.jpg" width="350px"> </div><br>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">rob</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pre2 = <span class="number">0</span>, pre1 = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> cur = Math.max(pre2 + nums[i], pre1);</span><br><span class="line">        pre2 = pre1;</span><br><span class="line">        pre1 = cur;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pre1;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="3-强盗在环形街区抢劫"><a href="#3-强盗在环形街区抢劫" class="headerlink" title="3. 强盗在环形街区抢劫"></a>3. 强盗在环形街区抢劫</h3><p>213. House Robber II (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/house-robber-ii/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/house-robber-ii/description/">力扣</a></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">rob</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums == <span class="keyword">null</span> || nums.length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> n = nums.length;</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> nums[<span class="number">0</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Math.max(rob(nums, <span class="number">0</span>, n - <span class="number">2</span>), rob(nums, <span class="number">1</span>, n - <span class="number">1</span>));</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">rob</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> first, <span class="keyword">int</span> last)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pre2 = <span class="number">0</span>, pre1 = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = first; i &lt;= last; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> cur = Math.max(pre1, pre2 + nums[i]);</span><br><span class="line">        pre2 = pre1;</span><br><span class="line">        pre1 = cur;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pre1;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="4-信件错排"><a href="#4-信件错排" class="headerlink" title="4. 信件错排"></a>4. 信件错排</h3><p>题目描述：有 N 个 信 和 信封，它们被打乱，求错误装信方式的数量。</p>
<p>定义一个数组 dp 存储错误方式数量，dp[i] 表示前 i 个信和信封的错误方式数量。假设第 i 个信装到第 j 个信封里面，而第 j 个信装到第 k 个信封里面。根据 i 和 k 是否相等，有两种情况：</p>
<ul>
<li>i==k，交换 i 和 j 的信后，它们的信和信封在正确的位置，但是其余 i-2 封信有 dp[i-2] 种错误装信的方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-2] 种错误装信方式。</li>
<li>i != k，交换 i 和 j 的信后，第 i 个信和信封在正确的位置，其余 i-1 封信有 dp[i-1] 种错误装信方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-1] 种错误装信方式。</li>
</ul>
<p>综上所述，错误装信数量方式数量为：</p>
<!--<div align="center"><img src= "" data-lazy-src="https://latex.codecogs.com/gif.latex?dp[i]=(i-1)*dp[i-2]+(i-1)*dp[i-1]" class="mathjax-pic"/></div> <br>-->

<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/da1f96b9-fd4d-44ca-8925-fb14c5733388.png" width="350px"> </div><br>

<h3 id="5-母牛生产"><a href="#5-母牛生产" class="headerlink" title="5. 母牛生产"></a>5. 母牛生产</h3><p><a href="#">程序员代码面试指南-P181</a></p>
<p>题目描述：假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。</p>
<p>第 i 年成熟的牛的数量为：</p>
<!--<div align="center"><img src= "" data-lazy-src="https://latex.codecogs.com/gif.latex?dp[i]=dp[i-1]+dp[i-3]" class="mathjax-pic"/></div> <br>-->

<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/879814ee-48b5-4bcb-86f5-dcc400cb81ad.png" width="250px"> </div><br>

<h2 id="矩阵路径"><a href="#矩阵路径" class="headerlink" title="矩阵路径"></a>矩阵路径</h2><h3 id="1-矩阵的最小路径和"><a href="#1-矩阵的最小路径和" class="headerlink" title="1. 矩阵的最小路径和"></a>1. 矩阵的最小路径和</h3><p>64. Minimum Path Sum (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/minimum-path-sum/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/minimum-path-sum/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">[[1,3,1],</span><br><span class="line"> [1,5,1],</span><br><span class="line"> [4,2,1]]</span><br><span class="line">Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.</span><br></pre></td></tr></table></figure>

<p>题目描述：求从矩阵的左上角到右下角的最小路径和，每次只能向右和向下移动。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minPathSum</span><span class="params">(<span class="keyword">int</span>[][] grid)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (grid.length == <span class="number">0</span> || grid[<span class="number">0</span>].length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> m = grid.length, n = grid[<span class="number">0</span>].length;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (j == <span class="number">0</span>) &#123;</span><br><span class="line">                dp[j] = dp[j];        <span class="comment">// 只能从上侧走到该位置</span></span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (i == <span class="number">0</span>) &#123;</span><br><span class="line">                dp[j] = dp[j - <span class="number">1</span>];    <span class="comment">// 只能从左侧走到该位置</span></span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                dp[j] = Math.min(dp[j - <span class="number">1</span>], dp[j]);</span><br><span class="line">            &#125;</span><br><span class="line">            dp[j] += grid[i][j];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n - <span class="number">1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-矩阵的总路径数"><a href="#2-矩阵的总路径数" class="headerlink" title="2. 矩阵的总路径数"></a>2. 矩阵的总路径数</h3><p>62. Unique Paths (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/unique-paths/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/unique-paths/description/">力扣</a></p>
<p>题目描述：统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动。</p>
<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/dc82f0f3-c1d4-4ac8-90ac-d5b32a9bd75a.jpg" width=""> </div><br>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">uniquePaths</span><span class="params">(<span class="keyword">int</span> m, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    Arrays.fill(dp, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; n; j++) &#123;</span><br><span class="line">            dp[j] = dp[j] + dp[j - <span class="number">1</span>];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n - <span class="number">1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>也可以直接用数学公式求解，这是一个组合问题。机器人总共移动的次数 S=m+n-2，向下移动的次数 D=m-1，那么问题可以看成从 S 中取出 D 个位置的组合数量，这个问题的解为 C(S, D)。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">uniquePaths</span><span class="params">(<span class="keyword">int</span> m, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> S = m + n - <span class="number">2</span>;  <span class="comment">// 总共的移动次数</span></span><br><span class="line">    <span class="keyword">int</span> D = m - <span class="number">1</span>;      <span class="comment">// 向下的移动次数</span></span><br><span class="line">    <span class="keyword">long</span> ret = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= D; i++) &#123;</span><br><span class="line">        ret = ret * (S - D + i) / i;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> (<span class="keyword">int</span>) ret;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="数组区间"><a href="#数组区间" class="headerlink" title="数组区间"></a>数组区间</h2><h3 id="1-数组区间和"><a href="#1-数组区间和" class="headerlink" title="1. 数组区间和"></a>1. 数组区间和</h3><p>303. Range Sum Query - Immutable (Easy)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/range-sum-query-immutable/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/range-sum-query-immutable/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Given nums = [-2, 0, 3, -5, 2, -1]</span><br><span class="line"></span><br><span class="line">sumRange(0, 2) -&gt; 1</span><br><span class="line">sumRange(2, 5) -&gt; -1</span><br><span class="line">sumRange(0, 5) -&gt; -3</span><br></pre></td></tr></table></figure>

<p>求区间 i ~ j 的和，可以转换为 sum[j + 1] - sum[i]，其中 sum[i] 为 0 ~ i - 1 的和。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">NumArray</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] sums;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">NumArray</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        sums = <span class="keyword">new</span> <span class="keyword">int</span>[nums.length + <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= nums.length; i++) &#123;</span><br><span class="line">            sums[i] = sums[i - <span class="number">1</span>] + nums[i - <span class="number">1</span>];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">sumRange</span><span class="params">(<span class="keyword">int</span> i, <span class="keyword">int</span> j)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> sums[j + <span class="number">1</span>] - sums[i];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-数组中等差递增子区间的个数"><a href="#2-数组中等差递增子区间的个数" class="headerlink" title="2. 数组中等差递增子区间的个数"></a>2. 数组中等差递增子区间的个数</h3><p>413. Arithmetic Slices (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/arithmetic-slices/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/arithmetic-slices/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">A = [0, 1, 2, 3, 4]</span><br><span class="line"></span><br><span class="line">return: 6, for 3 arithmetic slices in A:</span><br><span class="line"></span><br><span class="line">[0, 1, 2],</span><br><span class="line">[1, 2, 3],</span><br><span class="line">[0, 1, 2, 3],</span><br><span class="line">[0, 1, 2, 3, 4],</span><br><span class="line">[ 1, 2, 3, 4],</span><br><span class="line">[2, 3, 4]</span><br></pre></td></tr></table></figure>

<p>dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。</p>
<p>当 A[i] - A[i-1] == A[i-1] - A[i-2]，那么 [A[i-2], A[i-1], A[i]] 构成一个等差递增子区间。而且在以 A[i-1] 为结尾的递增子区间的后面再加上一个 A[i]，一样可以构成新的递增子区间。</p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">dp[2] = 1</span><br><span class="line">    [0, 1, 2]</span><br><span class="line">dp[3] = dp[2] + 1 = 2</span><br><span class="line">    [0, 1, 2, 3], // [0, 1, 2] 之后加一个 3</span><br><span class="line">    [1, 2, 3]     // 新的递增子区间</span><br><span class="line">dp[4] = dp[3] + 1 = 3</span><br><span class="line">    [0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4</span><br><span class="line">    [1, 2, 3, 4],    // [1, 2, 3] 之后加一个 4</span><br><span class="line">    [2, 3, 4]        // 新的递增子区间</span><br></pre></td></tr></table></figure>

<p>综上，在 A[i] - A[i-1] == A[i-1] - A[i-2] 时，dp[i] = dp[i-1] + 1。</p>
<p>因为递增子区间不一定以最后一个元素为结尾，可以是任意一个元素结尾，因此需要返回 dp 数组累加的结果。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numberOfArithmeticSlices</span><span class="params">(<span class="keyword">int</span>[] A)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (A == <span class="keyword">null</span> || A.length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> n = A.length;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (A[i] - A[i - <span class="number">1</span>] == A[i - <span class="number">1</span>] - A[i - <span class="number">2</span>]) &#123;</span><br><span class="line">            dp[i] = dp[i - <span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> total = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> cnt : dp) &#123;</span><br><span class="line">        total += cnt;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> total;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="分割整数"><a href="#分割整数" class="headerlink" title="分割整数"></a>分割整数</h2><h3 id="1-分割整数的最大乘积"><a href="#1-分割整数的最大乘积" class="headerlink" title="1. 分割整数的最大乘积"></a>1. 分割整数的最大乘积</h3><p>343. Integer Break (Medim)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/integer-break/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/integer-break/description/">力扣</a></p>
<p>题目描述：For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">integerBreak</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n + <span class="number">1</span>];</span><br><span class="line">    dp[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= i - <span class="number">1</span>; j++) &#123;</span><br><span class="line">            dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-按平方数来分割整数"><a href="#2-按平方数来分割整数" class="headerlink" title="2. 按平方数来分割整数"></a>2. 按平方数来分割整数</h3><p>279. Perfect Squares(Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/perfect-squares/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/perfect-squares/description/">力扣</a></p>
<p>题目描述：For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numSquares</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    List&lt;Integer&gt; squareList = generateSquareList(n);</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> min = Integer.MAX_VALUE;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> square : squareList) &#123;</span><br><span class="line">            <span class="keyword">if</span> (square &gt; i) &#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            min = Math.min(min, dp[i - square] + <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        dp[i] = min;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> List&lt;Integer&gt; <span class="title">generateSquareList</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    List&lt;Integer&gt; squareList = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> diff = <span class="number">3</span>;</span><br><span class="line">    <span class="keyword">int</span> square = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (square &lt;= n) &#123;</span><br><span class="line">        squareList.add(square);</span><br><span class="line">        square += diff;</span><br><span class="line">        diff += <span class="number">2</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> squareList;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="3-分割整数构成字母字符串"><a href="#3-分割整数构成字母字符串" class="headerlink" title="3. 分割整数构成字母字符串"></a>3. 分割整数构成字母字符串</h3><p>91. Decode Ways (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/decode-ways/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/decode-ways/description/">力扣</a></p>
<p>题目描述：Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numDecodings</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s == <span class="keyword">null</span> || s.length() == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> n = s.length();</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n + <span class="number">1</span>];</span><br><span class="line">    dp[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">    dp[<span class="number">1</span>] = s.charAt(<span class="number">0</span>) == <span class="string">&#x27;0&#x27;</span> ? <span class="number">0</span> : <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> one = Integer.valueOf(s.substring(i - <span class="number">1</span>, i));</span><br><span class="line">        <span class="keyword">if</span> (one != <span class="number">0</span>) &#123;</span><br><span class="line">            dp[i] += dp[i - <span class="number">1</span>];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (s.charAt(i - <span class="number">2</span>) == <span class="string">&#x27;0&#x27;</span>) &#123;</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span> two = Integer.valueOf(s.substring(i - <span class="number">2</span>, i));</span><br><span class="line">        <span class="keyword">if</span> (two &lt;= <span class="number">26</span>) &#123;</span><br><span class="line">            dp[i] += dp[i - <span class="number">2</span>];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="最长递增子序列"><a href="#最长递增子序列" class="headerlink" title="最长递增子序列"></a>最长递增子序列</h2><p>已知一个序列 {S<sub>1</sub>, S<sub>2</sub>,…,S<sub>n</sub>}，取出若干数组成新的序列 {S<sub>i1</sub>, S<sub>i2</sub>,…, S<sub>im</sub>}，其中 i1、i2 … im 保持递增，即新序列中各个数仍然保持原数列中的先后顺序，称新序列为原序列的一个  <strong>子序列</strong>  。</p>
<p>如果在子序列中，当下标 ix &gt; iy 时，S<sub>ix</sub> &gt; S<sub>iy</sub>，称子序列为原序列的一个  <strong>递增子序列</strong>  。</p>
<p>定义一个数组 dp 存储最长递增子序列的长度，dp[n] 表示以 S<sub>n</sub> 结尾的序列的最长递增子序列长度。对于一个递增子序列 {S<sub>i1</sub>, S<sub>i2</sub>,…,S<sub>im</sub>}，如果 im &lt; n 并且 S<sub>im</sub> &lt; S<sub>n</sub>，此时 {S<sub>i1</sub>, S<sub>i2</sub>,…, S<sub>im</sub>, S<sub>n</sub>} 为一个递增子序列，递增子序列的长度增加 1。满足上述条件的递增子序列中，长度最长的那个递增子序列就是要找的，在长度最长的递增子序列上加上 S<sub>n</sub> 就构成了以 S<sub>n</sub> 为结尾的最长递增子序列。因此 dp[n] = max{ dp[i]+1 | S<sub>i</sub> &lt; S<sub>n</sub> &amp;&amp; i &lt; n} 。</p>
<p>因为在求 dp[n] 时可能无法找到一个满足条件的递增子序列，此时 {S<sub>n</sub>} 就构成了递增子序列，需要对前面的求解方程做修改，令 dp[n] 最小为 1，即：</p>
<!--<div align="center"><img src= "" data-lazy-src="https://latex.codecogs.com/gif.latex?dp[n]=max\{1,dp[i]+1|S_i<S_n\&\&i<n\}" class="mathjax-pic"/></div> <br>-->

<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/ee994da4-0fc7-443d-ac56-c08caf00a204.jpg" width="350px"> </div><br>

<p>对于一个长度为 N 的序列，最长递增子序列并不一定会以 S<sub>N</sub> 为结尾，因此 dp[N] 不是序列的最长递增子序列的长度，需要遍历 dp 数组找出最大值才是所要的结果，max{ dp[i] | 1 &lt;= i &lt;= N} 即为所求。</p>
<h3 id="1-最长递增子序列"><a href="#1-最长递增子序列" class="headerlink" title="1. 最长递增子序列"></a>1. 最长递增子序列</h3><p>300. Longest Increasing Subsequence (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/longest-increasing-subsequence/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-increasing-subsequence/description/">力扣</a></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lengthOfLIS</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = nums.length;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> max = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; i; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[i] &gt; nums[j]) &#123;</span><br><span class="line">                max = Math.max(max, dp[j] + <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        dp[i] = max;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Arrays.stream(dp).max().orElse(<span class="number">0</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>使用 Stream 求最大值会导致运行时间过长，可以改成以下形式：</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">int</span> ret = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">    ret = Math.max(ret, dp[i]);</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">return</span> ret;</span><br></pre></td></tr></table></figure>

<p>以上解法的时间复杂度为 O(N<sup>2</sup>)，可以使用二分查找将时间复杂度降低为 O(NlogN)。</p>
<p>定义一个 tails 数组，其中 tails[i] 存储长度为 i + 1 的最长递增子序列的最后一个元素。对于一个元素 x，</p>
<ul>
<li>如果它大于 tails 数组所有的值，那么把它添加到 tails 后面，表示最长递增子序列长度加 1；</li>
<li>如果 tails[i-1] &lt; x &lt;= tails[i]，那么更新 tails[i] = x。</li>
</ul>
<p>例如对于数组 [4,3,6,5]，有：</p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">tails      len      num</span><br><span class="line">[]         0        4</span><br><span class="line">[4]        1        3</span><br><span class="line">[3]        1        6</span><br><span class="line">[3,6]      2        5</span><br><span class="line">[3,5]      2        null</span><br></pre></td></tr></table></figure>

<p>可以看出 tails 数组保持有序，因此在查找 S<sub>i</sub> 位于 tails 数组的位置时就可以使用二分查找。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lengthOfLIS</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = nums.length;</span><br><span class="line">    <span class="keyword">int</span>[] tails = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">int</span> len = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) &#123;</span><br><span class="line">        <span class="keyword">int</span> index = binarySearch(tails, len, num);</span><br><span class="line">        tails[index] = num;</span><br><span class="line">        <span class="keyword">if</span> (index == len) &#123;</span><br><span class="line">            len++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> len;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(<span class="keyword">int</span>[] tails, <span class="keyword">int</span> len, <span class="keyword">int</span> key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> l = <span class="number">0</span>, h = len;</span><br><span class="line">    <span class="keyword">while</span> (l &lt; h) &#123;</span><br><span class="line">        <span class="keyword">int</span> mid = l + (h - l) / <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">if</span> (tails[mid] == key) &#123;</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (tails[mid] &gt; key) &#123;</span><br><span class="line">            h = mid;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            l = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> l;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-一组整数对能够构成的最长链"><a href="#2-一组整数对能够构成的最长链" class="headerlink" title="2. 一组整数对能够构成的最长链"></a>2. 一组整数对能够构成的最长链</h3><p>646. Maximum Length of Pair Chain (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/maximum-length-of-pair-chain/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-length-of-pair-chain/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Input: [[1,2], [2,3], [3,4]]</span><br><span class="line">Output: 2</span><br><span class="line">Explanation: The longest chain is [1,2] -&gt; [3,4]</span><br></pre></td></tr></table></figure>

<p>题目描述：对于 (a, b) 和 (c, d) ，如果 b &lt; c，则它们可以构成一条链。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findLongestChain</span><span class="params">(<span class="keyword">int</span>[][] pairs)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (pairs == <span class="keyword">null</span> || pairs.length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Arrays.sort(pairs, (a, b) -&gt; (a[<span class="number">0</span>] - b[<span class="number">0</span>]));</span><br><span class="line">    <span class="keyword">int</span> n = pairs.length;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    Arrays.fill(dp, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; i; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (pairs[j][<span class="number">1</span>] &lt; pairs[i][<span class="number">0</span>]) &#123;</span><br><span class="line">                dp[i] = Math.max(dp[i], dp[j] + <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Arrays.stream(dp).max().orElse(<span class="number">0</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="3-最长摆动子序列"><a href="#3-最长摆动子序列" class="headerlink" title="3. 最长摆动子序列"></a>3. 最长摆动子序列</h3><p>376. Wiggle Subsequence (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/wiggle-subsequence/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/wiggle-subsequence/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Input: [1,7,4,9,2,5]</span><br><span class="line">Output: 6</span><br><span class="line">The entire sequence is a wiggle sequence.</span><br><span class="line"></span><br><span class="line">Input: [1,17,5,10,13,15,10,5,16,8]</span><br><span class="line">Output: 7</span><br><span class="line">There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].</span><br><span class="line"></span><br><span class="line">Input: [1,2,3,4,5,6,7,8,9]</span><br><span class="line">Output: 2</span><br></pre></td></tr></table></figure>

<p>要求：使用 O(N) 时间复杂度求解。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">wiggleMaxLength</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums == <span class="keyword">null</span> || nums.length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> up = <span class="number">1</span>, down = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (nums[i] &gt; nums[i - <span class="number">1</span>]) &#123;</span><br><span class="line">            up = down + <span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (nums[i] &lt; nums[i - <span class="number">1</span>]) &#123;</span><br><span class="line">            down = up + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Math.max(up, down);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="最长公共子序列"><a href="#最长公共子序列" class="headerlink" title="最长公共子序列"></a>最长公共子序列</h2><p>对于两个子序列 S1 和 S2，找出它们最长的公共子序列。</p>
<p>定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1<sub>i</sub> 与 S2<sub>j</sub> 值是否相等，分为两种情况：</p>
<ul>
<li>当 S1<sub>i</sub>==S2<sub>j</sub> 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1<sub>i</sub> 这个值，最长公共子序列长度加 1，即 dp[i][j] = dp[i-1][j-1] + 1。</li>
<li>当 S1<sub>i</sub> != S2<sub>j</sub> 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。</li>
</ul>
<p>综上，最长公共子序列的状态转移方程为：</p>
<!--<div align="center"><img src= "" data-lazy-src="https://latex.codecogs.com/gif.latex?dp[i][j]=\left\{\begin{array}{rcl}dp[i-1][j-1]&&{S1_i==S2_j}\\max(dp[i-1][j],dp[i][j-1])&&{S1_i<>S2_j}\end{array}\right." class="mathjax-pic"/></div> <br>-->

<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/ecd89a22-c075-4716-8423-e0ba89230e9a.jpg" width="450px"> </div><br>

<p>对于长度为 N 的序列 S<sub>1</sub> 和长度为 M 的序列 S<sub>2</sub>，dp[N][M] 就是序列 S<sub>1</sub> 和序列 S<sub>2</sub> 的最长公共子序列长度。</p>
<p>与最长递增子序列相比，最长公共子序列有以下不同点：</p>
<ul>
<li>针对的是两个序列，求它们的最长公共子序列。</li>
<li>在最长递增子序列中，dp[i] 表示以 S<sub>i</sub> 为结尾的最长递增子序列长度，子序列必须包含 S<sub>i</sub> ；在最长公共子序列中，dp[i][j] 表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度，不一定包含 S1<sub>i</sub> 和 S2<sub>j</sub>。</li>
<li>在求最终解时，最长公共子序列中 dp[N][M] 就是最终解，而最长递增子序列中 dp[N] 不是最终解，因为以 S<sub>N</sub> 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。</li>
</ul>
<h3 id="1-最长公共子序列"><a href="#1-最长公共子序列" class="headerlink" title="1. 最长公共子序列"></a>1. 最长公共子序列</h3><p>1143. Longest Common Subsequence</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/longest-common-subsequence/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-common-subsequence/">力扣</a></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestCommonSubsequence</span><span class="params">(String text1, String text2)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n1 = text1.length(), n2 = text2.length();</span><br><span class="line">    <span class="keyword">int</span>[][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n1 + <span class="number">1</span>][n2 + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n1; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= n2; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (text1.charAt(i - <span class="number">1</span>) == text2.charAt(j - <span class="number">1</span>)) &#123;</span><br><span class="line">                dp[i][j] = dp[i - <span class="number">1</span>][j - <span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                dp[i][j] = Math.max(dp[i - <span class="number">1</span>][j], dp[i][j - <span class="number">1</span>]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n1][n2];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="0-1-背包"><a href="#0-1-背包" class="headerlink" title="0-1 背包"></a>0-1 背包</h2><p>有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。</p>
<p>定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：</p>
<ul>
<li>第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。</li>
<li>第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。</li>
</ul>
<p>第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：</p>
<!--<div align="center"><img src= "" data-lazy-src="https://latex.codecogs.com/gif.latex?dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)" class="mathjax-pic"/></div> <br>-->

<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/8cb2be66-3d47-41ba-b55b-319fc68940d4.png" width="400px"> </div><br>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">// W 为背包总体积</span></span><br><span class="line"><span class="comment">// N 为物品数量</span></span><br><span class="line"><span class="comment">// weights 数组存储 N 个物品的重量</span></span><br><span class="line"><span class="comment">// values 数组存储 N 个物品的价值</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">knapsack</span><span class="params">(<span class="keyword">int</span> W, <span class="keyword">int</span> N, <span class="keyword">int</span>[] weights, <span class="keyword">int</span>[] values)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[N + <span class="number">1</span>][W + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= N; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> w = weights[i - <span class="number">1</span>], v = values[i - <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= W; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (j &gt;= w) &#123;</span><br><span class="line">                dp[i][j] = Math.max(dp[i - <span class="number">1</span>][j], dp[i - <span class="number">1</span>][j - w] + v);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                dp[i][j] = dp[i - <span class="number">1</span>][j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[N][W];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>空间优化</strong>  </p>
<p>在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，</p>
<!--<div align="center"><img src= "" data-lazy-src="https://latex.codecogs.com/gif.latex?dp[j]=max(dp[j],dp[j-w]+v)" class="mathjax-pic"/></div> <br>-->

<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/9ae89f16-7905-4a6f-88a2-874b4cac91f4.jpg" width="300px"> </div><br>

<p>因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，防止将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">knapsack</span><span class="params">(<span class="keyword">int</span> W, <span class="keyword">int</span> N, <span class="keyword">int</span>[] weights, <span class="keyword">int</span>[] values)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[W + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= N; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> w = weights[i - <span class="number">1</span>], v = values[i - <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = W; j &gt;= <span class="number">1</span>; j--) &#123;</span><br><span class="line">            <span class="keyword">if</span> (j &gt;= w) &#123;</span><br><span class="line">                dp[j] = Math.max(dp[j], dp[j - w] + v);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[W];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>无法使用贪心算法的解释</strong>  </p>
<p>0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.</p>
<table>
<thead>
<tr>
<th>id</th>
<th>w</th>
<th>v</th>
<th>v/w</th>
</tr>
</thead>
<tbody><tr>
<td>0</td>
<td>1</td>
<td>6</td>
<td>6</td>
</tr>
<tr>
<td>1</td>
<td>2</td>
<td>10</td>
<td>5</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>12</td>
<td>4</td>
</tr>
</tbody></table>
<p><strong>变种</strong>  </p>
<ul>
<li><p>完全背包：物品数量为无限个</p>
</li>
<li><p>多重背包：物品数量有限制</p>
</li>
<li><p>多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制</p>
</li>
<li><p>其它：物品之间相互约束或者依赖</p>
</li>
</ul>
<h3 id="1-划分数组为和相等的两部分"><a href="#1-划分数组为和相等的两部分" class="headerlink" title="1. 划分数组为和相等的两部分"></a>1. 划分数组为和相等的两部分</h3><p>416. Partition Equal Subset Sum (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/partition-equal-subset-sum/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/partition-equal-subset-sum/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Input: [1, 5, 11, 5]</span><br><span class="line"></span><br><span class="line">Output: true</span><br><span class="line"></span><br><span class="line">Explanation: The array can be partitioned as [1, 5, 5] and [11].</span><br></pre></td></tr></table></figure>

<p>可以看成一个背包大小为 sum/2 的 0-1 背包问题。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canPartition</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sum = computeArraySum(nums);</span><br><span class="line">    <span class="keyword">if</span> (sum % <span class="number">2</span> != <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> W = sum / <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">boolean</span>[] dp = <span class="keyword">new</span> <span class="keyword">boolean</span>[W + <span class="number">1</span>];</span><br><span class="line">    dp[<span class="number">0</span>] = <span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) &#123;                 <span class="comment">// 0-1 背包一个物品只能用一次</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = W; i &gt;= num; i--) &#123;   <span class="comment">// 从后往前，先计算 dp[i] 再计算 dp[i-num]</span></span><br><span class="line">            dp[i] = dp[i] || dp[i - num];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[W];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">computeArraySum</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) &#123;</span><br><span class="line">        sum += num;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-改变一组数的正负号使得它们的和为一给定数"><a href="#2-改变一组数的正负号使得它们的和为一给定数" class="headerlink" title="2. 改变一组数的正负号使得它们的和为一给定数"></a>2. 改变一组数的正负号使得它们的和为一给定数</h3><p>494. Target Sum (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/target-sum/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/target-sum/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Input: nums is [1, 1, 1, 1, 1], S is 3.</span><br><span class="line">Output: 5</span><br><span class="line">Explanation:</span><br><span class="line"></span><br><span class="line">-1+1+1+1+1 = 3</span><br><span class="line">+1-1+1+1+1 = 3</span><br><span class="line">+1+1-1+1+1 = 3</span><br><span class="line">+1+1+1-1+1 = 3</span><br><span class="line">+1+1+1+1-1 = 3</span><br><span class="line"></span><br><span class="line">There are 5 ways to assign symbols to make the sum of nums be target 3.</span><br></pre></td></tr></table></figure>

<p>该问题可以转换为 Subset Sum 问题，从而使用 0-1 背包的方法来求解。</p>
<p>可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：</p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">                  sum(P) - sum(N) = target</span><br><span class="line">sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)</span><br><span class="line">                       2 * sum(P) = target + sum(nums)</span><br></pre></td></tr></table></figure>

<p>因此只要找到一个子集，令它们都取正号，并且和等于 (target + sum(nums))/2，就证明存在解。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findTargetSumWays</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sum = computeArraySum(nums);</span><br><span class="line">    <span class="keyword">if</span> (sum &lt; S || (sum + S) % <span class="number">2</span> == <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> W = (sum + S) / <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[W + <span class="number">1</span>];</span><br><span class="line">    dp[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = W; i &gt;= num; i--) &#123;</span><br><span class="line">            dp[i] = dp[i] + dp[i - num];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[W];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">computeArraySum</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) &#123;</span><br><span class="line">        sum += num;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>DFS 解法：</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findTargetSumWays</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> findTargetSumWays(nums, <span class="number">0</span>, S);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">findTargetSumWays</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> start, <span class="keyword">int</span> S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (start == nums.length) &#123;</span><br><span class="line">        <span class="keyword">return</span> S == <span class="number">0</span> ? <span class="number">1</span> : <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> findTargetSumWays(nums, start + <span class="number">1</span>, S + nums[start])</span><br><span class="line">            + findTargetSumWays(nums, start + <span class="number">1</span>, S - nums[start]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="3-01-字符构成最多的字符串"><a href="#3-01-字符构成最多的字符串" class="headerlink" title="3. 01 字符构成最多的字符串"></a>3. 01 字符构成最多的字符串</h3><p>474. Ones and Zeroes (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/ones-and-zeroes/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/ones-and-zeroes/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Input: Array = &#123;&quot;10&quot;, &quot;0001&quot;, &quot;111001&quot;, &quot;1&quot;, &quot;0&quot;&#125;, m = 5, n = 3</span><br><span class="line">Output: 4</span><br><span class="line"></span><br><span class="line">Explanation: There are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are &quot;10&quot;,&quot;0001&quot;,&quot;1&quot;,&quot;0&quot;</span><br></pre></td></tr></table></figure>

<p>这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMaxForm</span><span class="params">(String[] strs, <span class="keyword">int</span> m, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (strs == <span class="keyword">null</span> || strs.length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[m + <span class="number">1</span>][n + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (String s : strs) &#123;    <span class="comment">// 每个字符串只能用一次</span></span><br><span class="line">        <span class="keyword">int</span> ones = <span class="number">0</span>, zeros = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">char</span> c : s.toCharArray()) &#123;</span><br><span class="line">            <span class="keyword">if</span> (c == <span class="string">&#x27;0&#x27;</span>) &#123;</span><br><span class="line">                zeros++;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                ones++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = m; i &gt;= zeros; i--) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = n; j &gt;= ones; j--) &#123;</span><br><span class="line">                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[m][n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="4-找零钱的最少硬币数"><a href="#4-找零钱的最少硬币数" class="headerlink" title="4. 找零钱的最少硬币数"></a>4. 找零钱的最少硬币数</h3><p>322. Coin Change (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/coin-change/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/coin-change/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Example 1:</span><br><span class="line">coins = [1, 2, 5], amount = 11</span><br><span class="line">return 3 (11 = 5 + 5 + 1)</span><br><span class="line"></span><br><span class="line">Example 2:</span><br><span class="line">coins = [2], amount = 3</span><br><span class="line">return -1.</span><br></pre></td></tr></table></figure>

<p>题目描述：给一些面额的硬币，要求用这些硬币来组成给定面额的钱数，并且使得硬币数量最少。硬币可以重复使用。</p>
<ul>
<li>物品：硬币</li>
<li>物品大小：面额</li>
<li>物品价值：数量</li>
</ul>
<p>因为硬币可以重复使用，因此这是一个完全背包问题。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历即可。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">coinChange</span><span class="params">(<span class="keyword">int</span>[] coins, <span class="keyword">int</span> amount)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (amount == <span class="number">0</span> || coins == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[amount + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> coin : coins) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = coin; i &lt;= amount; i++) &#123; <span class="comment">//将逆序遍历改为正序遍历</span></span><br><span class="line">            <span class="keyword">if</span> (i == coin) &#123;</span><br><span class="line">                dp[i] = <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (dp[i] == <span class="number">0</span> &amp;&amp; dp[i - coin] != <span class="number">0</span>) &#123;</span><br><span class="line">                dp[i] = dp[i - coin] + <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (dp[i - coin] != <span class="number">0</span>) &#123;</span><br><span class="line">                dp[i] = Math.min(dp[i], dp[i - coin] + <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[amount] == <span class="number">0</span> ? -<span class="number">1</span> : dp[amount];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="5-找零钱的硬币数组合"><a href="#5-找零钱的硬币数组合" class="headerlink" title="5. 找零钱的硬币数组合"></a>5. 找零钱的硬币数组合</h3><p>518. Coin Change 2 (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/coin-change-2/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/coin-change-2/description/">力扣</a></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">Input: amount = 5, coins = [1, 2, 5]</span><br><span class="line">Output: 4</span><br><span class="line">Explanation: there are four ways to make up the amount:</span><br><span class="line">5=5</span><br><span class="line">5=2+2+1</span><br><span class="line">5=2+1+1+1</span><br><span class="line">5=1+1+1+1+1</span><br></pre></td></tr></table></figure>

<p>完全背包问题，使用 dp 记录可达成目标的组合数目。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">change</span><span class="params">(<span class="keyword">int</span> amount, <span class="keyword">int</span>[] coins)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (coins == <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[amount + <span class="number">1</span>];</span><br><span class="line">    dp[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> coin : coins) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = coin; i &lt;= amount; i++) &#123;</span><br><span class="line">            dp[i] += dp[i - coin];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[amount];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="6-字符串按单词列表分割"><a href="#6-字符串按单词列表分割" class="headerlink" title="6. 字符串按单词列表分割"></a>6. 字符串按单词列表分割</h3><p>139. Word Break (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/word-break/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/word-break/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">s = &quot;leetcode&quot;,</span><br><span class="line">dict = [&quot;leet&quot;, &quot;code&quot;].</span><br><span class="line">Return true because &quot;leetcode&quot; can be segmented as &quot;leet code&quot;.</span><br></pre></td></tr></table></figure>

<p>dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。</p>
<p>该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中，例如下面的 dict 就不够组成字符串 “leetcode”：</p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">[&quot;lee&quot;, &quot;tc&quot;, &quot;cod&quot;]</span><br></pre></td></tr></table></figure>

<p>求解顺序的完全背包问题时，对物品的迭代应该放在最里层，对背包的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">wordBreak</span><span class="params">(String s, List&lt;String&gt; wordDict)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = s.length();</span><br><span class="line">    <span class="keyword">boolean</span>[] dp = <span class="keyword">new</span> <span class="keyword">boolean</span>[n + <span class="number">1</span>];</span><br><span class="line">    dp[<span class="number">0</span>] = <span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (String word : wordDict) &#123;   <span class="comment">// 对物品的迭代应该放在最里层</span></span><br><span class="line">            <span class="keyword">int</span> len = word.length();</span><br><span class="line">            <span class="keyword">if</span> (len &lt;= i &amp;&amp; word.equals(s.substring(i - len, i))) &#123;</span><br><span class="line">                dp[i] = dp[i] || dp[i - len];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="7-组合总和"><a href="#7-组合总和" class="headerlink" title="7. 组合总和"></a>7. 组合总和</h3><p>377. Combination Sum IV (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/combination-sum-iv/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/combination-sum-iv/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">nums = [1, 2, 3]</span><br><span class="line">target = 4</span><br><span class="line"></span><br><span class="line">The possible combination ways are:</span><br><span class="line">(1, 1, 1, 1)</span><br><span class="line">(1, 1, 2)</span><br><span class="line">(1, 2, 1)</span><br><span class="line">(1, 3)</span><br><span class="line">(2, 1, 1)</span><br><span class="line">(2, 2)</span><br><span class="line">(3, 1)</span><br><span class="line"></span><br><span class="line">Note that different sequences are counted as different combinations.</span><br><span class="line"></span><br><span class="line">Therefore the output is 7.</span><br></pre></td></tr></table></figure>

<p>涉及顺序的完全背包。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">combinationSum4</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums == <span class="keyword">null</span> || nums.length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] maximum = <span class="keyword">new</span> <span class="keyword">int</span>[target + <span class="number">1</span>];</span><br><span class="line">    maximum[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">    Arrays.sort(nums);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= target; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; nums.length &amp;&amp; nums[j] &lt;= i; j++) &#123;</span><br><span class="line">            maximum[i] += maximum[i - nums[j]];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> maximum[target];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="股票交易"><a href="#股票交易" class="headerlink" title="股票交易"></a>股票交易</h2><h3 id="1-需要冷却期的股票交易"><a href="#1-需要冷却期的股票交易" class="headerlink" title="1. 需要冷却期的股票交易"></a>1. 需要冷却期的股票交易</h3><p>309. Best Time to Buy and Sell Stock with Cooldown(Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/">力扣</a></p>
<p>题目描述：交易之后需要有一天的冷却时间。</p>
<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/ffd96b99-8009-487c-8e98-11c9d44ef14f.png" width="300px"> </div><br>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxProfit</span><span class="params">(<span class="keyword">int</span>[] prices)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (prices == <span class="keyword">null</span> || prices.length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> N = prices.length;</span><br><span class="line">    <span class="keyword">int</span>[] buy = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">    <span class="keyword">int</span>[] s1 = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">    <span class="keyword">int</span>[] sell = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">    <span class="keyword">int</span>[] s2 = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">    s1[<span class="number">0</span>] = buy[<span class="number">0</span>] = -prices[<span class="number">0</span>];</span><br><span class="line">    sell[<span class="number">0</span>] = s2[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; N; i++) &#123;</span><br><span class="line">        buy[i] = s2[i - <span class="number">1</span>] - prices[i];</span><br><span class="line">        s1[i] = Math.max(buy[i - <span class="number">1</span>], s1[i - <span class="number">1</span>]);</span><br><span class="line">        sell[i] = Math.max(buy[i - <span class="number">1</span>], s1[i - <span class="number">1</span>]) + prices[i];</span><br><span class="line">        s2[i] = Math.max(s2[i - <span class="number">1</span>], sell[i - <span class="number">1</span>]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Math.max(sell[N - <span class="number">1</span>], s2[N - <span class="number">1</span>]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-需要交易费用的股票交易"><a href="#2-需要交易费用的股票交易" class="headerlink" title="2. 需要交易费用的股票交易"></a>2. 需要交易费用的股票交易</h3><p>714. Best Time to Buy and Sell Stock with Transaction Fee (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Input: prices = [1, 3, 2, 8, 4, 9], fee = 2</span><br><span class="line">Output: 8</span><br><span class="line">Explanation: The maximum profit can be achieved by:</span><br><span class="line">Buying at prices[0] = 1</span><br><span class="line">Selling at prices[3] = 8</span><br><span class="line">Buying at prices[4] = 4</span><br><span class="line">Selling at prices[5] = 9</span><br><span class="line">The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.</span><br></pre></td></tr></table></figure>

<p>题目描述：每交易一次，都要支付一定的费用。</p>
<div align="center"> <img src= "" data-lazy-src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/1e2c588c-72b7-445e-aacb-d55dc8a88c29.png" width="300px"> </div><br>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxProfit</span><span class="params">(<span class="keyword">int</span>[] prices, <span class="keyword">int</span> fee)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> N = prices.length;</span><br><span class="line">    <span class="keyword">int</span>[] buy = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">    <span class="keyword">int</span>[] s1 = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">    <span class="keyword">int</span>[] sell = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">    <span class="keyword">int</span>[] s2 = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">    s1[<span class="number">0</span>] = buy[<span class="number">0</span>] = -prices[<span class="number">0</span>];</span><br><span class="line">    sell[<span class="number">0</span>] = s2[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; N; i++) &#123;</span><br><span class="line">        buy[i] = Math.max(sell[i - <span class="number">1</span>], s2[i - <span class="number">1</span>]) - prices[i];</span><br><span class="line">        s1[i] = Math.max(buy[i - <span class="number">1</span>], s1[i - <span class="number">1</span>]);</span><br><span class="line">        sell[i] = Math.max(buy[i - <span class="number">1</span>], s1[i - <span class="number">1</span>]) - fee + prices[i];</span><br><span class="line">        s2[i] = Math.max(s2[i - <span class="number">1</span>], sell[i - <span class="number">1</span>]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Math.max(sell[N - <span class="number">1</span>], s2[N - <span class="number">1</span>]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h3 id="3-只能进行两次的股票交易"><a href="#3-只能进行两次的股票交易" class="headerlink" title="3. 只能进行两次的股票交易"></a>3. 只能进行两次的股票交易</h3><p>123. Best Time to Buy and Sell Stock III (Hard)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/description/">力扣</a></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxProfit</span><span class="params">(<span class="keyword">int</span>[] prices)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> firstBuy = Integer.MIN_VALUE, firstSell = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> secondBuy = Integer.MIN_VALUE, secondSell = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> curPrice : prices) &#123;</span><br><span class="line">        <span class="keyword">if</span> (firstBuy &lt; -curPrice) &#123;</span><br><span class="line">            firstBuy = -curPrice;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (firstSell &lt; firstBuy + curPrice) &#123;</span><br><span class="line">            firstSell = firstBuy + curPrice;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (secondBuy &lt; firstSell - curPrice) &#123;</span><br><span class="line">            secondBuy = firstSell - curPrice;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (secondSell &lt; secondBuy + curPrice) &#123;</span><br><span class="line">            secondSell = secondBuy + curPrice;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> secondSell;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="4-只能进行-k-次的股票交易"><a href="#4-只能进行-k-次的股票交易" class="headerlink" title="4. 只能进行 k 次的股票交易"></a>4. 只能进行 k 次的股票交易</h3><p>188. Best Time to Buy and Sell Stock IV (Hard)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/description/">力扣</a></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxProfit</span><span class="params">(<span class="keyword">int</span> k, <span class="keyword">int</span>[] prices)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = prices.length;</span><br><span class="line">    <span class="keyword">if</span> (k &gt;= n / <span class="number">2</span>) &#123;   <span class="comment">// 这种情况下该问题退化为普通的股票交易问题</span></span><br><span class="line">        <span class="keyword">int</span> maxProfit = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (prices[i] &gt; prices[i - <span class="number">1</span>]) &#123;</span><br><span class="line">                maxProfit += prices[i] - prices[i - <span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> maxProfit;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[][] maxProfit = <span class="keyword">new</span> <span class="keyword">int</span>[k + <span class="number">1</span>][n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= k; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> localMax = maxProfit[i - <span class="number">1</span>][<span class="number">0</span>] - prices[<span class="number">0</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; n; j++) &#123;</span><br><span class="line">            maxProfit[i][j] = Math.max(maxProfit[i][j - <span class="number">1</span>], prices[j] + localMax);</span><br><span class="line">            localMax = Math.max(localMax, maxProfit[i - <span class="number">1</span>][j] - prices[j]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> maxProfit[k][n - <span class="number">1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="字符串编辑"><a href="#字符串编辑" class="headerlink" title="字符串编辑"></a>字符串编辑</h2><h3 id="1-删除两个字符串的字符使它们相等"><a href="#1-删除两个字符串的字符使它们相等" class="headerlink" title="1. 删除两个字符串的字符使它们相等"></a>1. 删除两个字符串的字符使它们相等</h3><p>583. Delete Operation for Two Strings (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/delete-operation-for-two-strings/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/delete-operation-for-two-strings/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Input: &quot;sea&quot;, &quot;eat&quot;</span><br><span class="line">Output: 2</span><br><span class="line">Explanation: You need one step to make &quot;sea&quot; to &quot;ea&quot; and another step to make &quot;eat&quot; to &quot;ea&quot;.</span><br></pre></td></tr></table></figure>

<p>可以转换为求两个字符串的最长公共子序列问题。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minDistance</span><span class="params">(String word1, String word2)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> m = word1.length(), n = word2.length();</span><br><span class="line">    <span class="keyword">int</span>[][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[m + <span class="number">1</span>][n + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (word1.charAt(i - <span class="number">1</span>) == word2.charAt(j - <span class="number">1</span>)) &#123;</span><br><span class="line">                dp[i][j] = dp[i - <span class="number">1</span>][j - <span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                dp[i][j] = Math.max(dp[i][j - <span class="number">1</span>], dp[i - <span class="number">1</span>][j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> m + n - <span class="number">2</span> * dp[m][n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-编辑距离"><a href="#2-编辑距离" class="headerlink" title="2. 编辑距离"></a>2. 编辑距离</h3><p>72. Edit Distance (Hard)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/edit-distance/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/edit-distance/description/">力扣</a></p>
<figure class="highlight html"><table><tr><td class="code"><pre><span class="line">Example 1:</span><br><span class="line"></span><br><span class="line">Input: word1 = &quot;horse&quot;, word2 = &quot;ros&quot;</span><br><span class="line">Output: 3</span><br><span class="line">Explanation:</span><br><span class="line">horse -&gt; rorse (replace &#x27;h&#x27; with &#x27;r&#x27;)</span><br><span class="line">rorse -&gt; rose (remove &#x27;r&#x27;)</span><br><span class="line">rose -&gt; ros (remove &#x27;e&#x27;)</span><br><span class="line">Example 2:</span><br><span class="line"></span><br><span class="line">Input: word1 = &quot;intention&quot;, word2 = &quot;execution&quot;</span><br><span class="line">Output: 5</span><br><span class="line">Explanation:</span><br><span class="line">intention -&gt; inention (remove &#x27;t&#x27;)</span><br><span class="line">inention -&gt; enention (replace &#x27;i&#x27; with &#x27;e&#x27;)</span><br><span class="line">enention -&gt; exention (replace &#x27;n&#x27; with &#x27;x&#x27;)</span><br><span class="line">exention -&gt; exection (replace &#x27;n&#x27; with &#x27;c&#x27;)</span><br><span class="line">exection -&gt; execution (insert &#x27;u&#x27;)</span><br></pre></td></tr></table></figure>

<p>题目描述：修改一个字符串成为另一个字符串，使得修改次数最少。一次修改操作包括：插入一个字符、删除一个字符、替换一个字符。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minDistance</span><span class="params">(String word1, String word2)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (word1 == <span class="keyword">null</span> || word2 == <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> m = word1.length(), n = word2.length();</span><br><span class="line">    <span class="keyword">int</span>[][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[m + <span class="number">1</span>][n + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= m; i++) &#123;</span><br><span class="line">        dp[i][<span class="number">0</span>] = i;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        dp[<span class="number">0</span>][i] = i;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (word1.charAt(i - <span class="number">1</span>) == word2.charAt(j - <span class="number">1</span>)) &#123;</span><br><span class="line">                dp[i][j] = dp[i - <span class="number">1</span>][j - <span class="number">1</span>];</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                dp[i][j] = Math.min(dp[i - <span class="number">1</span>][j - <span class="number">1</span>], Math.min(dp[i][j - <span class="number">1</span>], dp[i - <span class="number">1</span>][j])) + <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[m][n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="3-复制粘贴字符"><a href="#3-复制粘贴字符" class="headerlink" title="3. 复制粘贴字符"></a>3. 复制粘贴字符</h3><p>650. 2 Keys Keyboard (Medium)</p>
<p><a target="_blank" rel="noopener" href="https://leetcode.com/problems/2-keys-keyboard/description/">Leetcode</a> / <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/2-keys-keyboard/description/">力扣</a></p>
<p>题目描述：最开始只有一个字符 A，问需要多少次操作能够得到 n 个字符 A，每次操作可以复制当前所有的字符，或者粘贴。</p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">Input: 3</span><br><span class="line">Output: 3</span><br><span class="line">Explanation:</span><br><span class="line">Intitally, we have one character &#x27;A&#x27;.</span><br><span class="line">In step 1, we use Copy All operation.</span><br><span class="line">In step 2, we use Paste operation to get &#x27;AA&#x27;.</span><br><span class="line">In step 3, we use Paste operation to get &#x27;AAA&#x27;.</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minSteps</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">1</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= Math.sqrt(n); i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (n % i == <span class="number">0</span>) <span class="keyword">return</span> i + minSteps(n / i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> n;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minSteps</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">int</span> h = (<span class="keyword">int</span>) Math.sqrt(n);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        dp[i] = i;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">2</span>; j &lt;= h; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (i % j == <span class="number">0</span>) &#123;</span><br><span class="line">                dp[i] = dp[j] + dp[i / j];</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">Zhang Shuo</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://zhang-shuo-fr.gitee.io/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">https://zhang-shuo-fr.gitee.io/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://zhang-shuo-fr.gitee.io/hexo3" target="_blank">Zhang Shuo'blog</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/hexo3/tags/Leetcode%E9%A2%98%E8%A7%A3/">Leetcode题解</a></div><div class="post_share"><div class="social-share" data-image="/hexo3/img/12.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button button--animated"><i class="fas fa-qrcode"></i> 打赏</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="/hexo3/img/wechat.jpg" target="_blank"><img class="post-qr-code-img" src= "" data-lazy-src="/hexo3/img/wechat.jpg" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/hexo3/img/alipay.jpg" target="_blank"><img class="post-qr-code-img" src= "" data-lazy-src="/hexo3/img/alipay.jpg" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%90%9C%E7%B4%A2/"><img class="prev-cover" src= "" data-lazy-src="/hexo3/img/11.jpg" onerror="onerror=null;src='/hexo3/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">Leetcode 题解 - 搜索</div></div></a></div><div class="next-post pull-right"><a href="/hexo3/2021/12/06/notes/Java%20%E8%99%9A%E6%8B%9F%E6%9C%BA/"><img class="next-cover" src= "" data-lazy-src="/hexo3/img/13.jpg" onerror="onerror=null;src='/hexo3/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">虚拟机</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/" title="Leetcode 题解 - 二分查找"><img class="cover" src= "" data-lazy-src="/hexo3/img/1.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">Leetcode 题解 - 二分查找</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E4%BD%8D%E8%BF%90%E7%AE%97/" title="Leetcode 题解 - 位运算"><img class="cover" src= "" data-lazy-src="/hexo3/img/18.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">Leetcode 题解 - 位运算</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%88%86%E6%B2%BB/" title="Leetcode 题解 - 分治"><img class="cover" src= "" data-lazy-src="/hexo3/img/8.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">Leetcode 题解 - 分治</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8F%8C%E6%8C%87%E9%92%88/" title="Leetcode 题解 - 双指针"><img class="cover" src= "" data-lazy-src="/hexo3/img/1.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">Leetcode 题解 - 双指针</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%93%88%E5%B8%8C%E8%A1%A8/" title="Leetcode 题解 - 哈希表"><img class="cover" src= "" data-lazy-src="/hexo3/img/12.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">Leetcode 题解 - 哈希表</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%9B%BE/" title="Leetcode 题解 - 图"><img class="cover" src= "" data-lazy-src="/hexo3/img/19.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">Leetcode 题解 - 图</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#Leetcode-%E9%A2%98%E8%A7%A3-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="toc-number">1.</span> <span class="toc-text">Leetcode 题解 - 动态规划</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97"><span class="toc-number">1.1.</span> <span class="toc-text">斐波那契数列</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E7%88%AC%E6%A5%BC%E6%A2%AF"><span class="toc-number">1.1.1.</span> <span class="toc-text">1. 爬楼梯</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E5%BC%BA%E7%9B%97%E6%8A%A2%E5%8A%AB"><span class="toc-number">1.1.2.</span> <span class="toc-text">2. 强盗抢劫</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-%E5%BC%BA%E7%9B%97%E5%9C%A8%E7%8E%AF%E5%BD%A2%E8%A1%97%E5%8C%BA%E6%8A%A2%E5%8A%AB"><span class="toc-number">1.1.3.</span> <span class="toc-text">3. 强盗在环形街区抢劫</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-%E4%BF%A1%E4%BB%B6%E9%94%99%E6%8E%92"><span class="toc-number">1.1.4.</span> <span class="toc-text">4. 信件错排</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-%E6%AF%8D%E7%89%9B%E7%94%9F%E4%BA%A7"><span class="toc-number">1.1.5.</span> <span class="toc-text">5. 母牛生产</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%9F%A9%E9%98%B5%E8%B7%AF%E5%BE%84"><span class="toc-number">1.2.</span> <span class="toc-text">矩阵路径</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E7%9F%A9%E9%98%B5%E7%9A%84%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E5%92%8C"><span class="toc-number">1.2.1.</span> <span class="toc-text">1. 矩阵的最小路径和</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E7%9F%A9%E9%98%B5%E7%9A%84%E6%80%BB%E8%B7%AF%E5%BE%84%E6%95%B0"><span class="toc-number">1.2.2.</span> <span class="toc-text">2. 矩阵的总路径数</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E7%BB%84%E5%8C%BA%E9%97%B4"><span class="toc-number">1.3.</span> <span class="toc-text">数组区间</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E6%95%B0%E7%BB%84%E5%8C%BA%E9%97%B4%E5%92%8C"><span class="toc-number">1.3.1.</span> <span class="toc-text">1. 数组区间和</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E6%95%B0%E7%BB%84%E4%B8%AD%E7%AD%89%E5%B7%AE%E9%80%92%E5%A2%9E%E5%AD%90%E5%8C%BA%E9%97%B4%E7%9A%84%E4%B8%AA%E6%95%B0"><span class="toc-number">1.3.2.</span> <span class="toc-text">2. 数组中等差递增子区间的个数</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%88%86%E5%89%B2%E6%95%B4%E6%95%B0"><span class="toc-number">1.4.</span> <span class="toc-text">分割整数</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E5%88%86%E5%89%B2%E6%95%B4%E6%95%B0%E7%9A%84%E6%9C%80%E5%A4%A7%E4%B9%98%E7%A7%AF"><span class="toc-number">1.4.1.</span> <span class="toc-text">1. 分割整数的最大乘积</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E6%8C%89%E5%B9%B3%E6%96%B9%E6%95%B0%E6%9D%A5%E5%88%86%E5%89%B2%E6%95%B4%E6%95%B0"><span class="toc-number">1.4.2.</span> <span class="toc-text">2. 按平方数来分割整数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-%E5%88%86%E5%89%B2%E6%95%B4%E6%95%B0%E6%9E%84%E6%88%90%E5%AD%97%E6%AF%8D%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="toc-number">1.4.3.</span> <span class="toc-text">3. 分割整数构成字母字符串</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-number">1.5.</span> <span class="toc-text">最长递增子序列</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-number">1.5.1.</span> <span class="toc-text">1. 最长递增子序列</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E4%B8%80%E7%BB%84%E6%95%B4%E6%95%B0%E5%AF%B9%E8%83%BD%E5%A4%9F%E6%9E%84%E6%88%90%E7%9A%84%E6%9C%80%E9%95%BF%E9%93%BE"><span class="toc-number">1.5.2.</span> <span class="toc-text">2. 一组整数对能够构成的最长链</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-%E6%9C%80%E9%95%BF%E6%91%86%E5%8A%A8%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-number">1.5.3.</span> <span class="toc-text">3. 最长摆动子序列</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-number">1.6.</span> <span class="toc-text">最长公共子序列</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-number">1.6.1.</span> <span class="toc-text">1. 最长公共子序列</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#0-1-%E8%83%8C%E5%8C%85"><span class="toc-number">1.7.</span> <span class="toc-text">0-1 背包</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E5%88%92%E5%88%86%E6%95%B0%E7%BB%84%E4%B8%BA%E5%92%8C%E7%9B%B8%E7%AD%89%E7%9A%84%E4%B8%A4%E9%83%A8%E5%88%86"><span class="toc-number">1.7.1.</span> <span class="toc-text">1. 划分数组为和相等的两部分</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E6%94%B9%E5%8F%98%E4%B8%80%E7%BB%84%E6%95%B0%E7%9A%84%E6%AD%A3%E8%B4%9F%E5%8F%B7%E4%BD%BF%E5%BE%97%E5%AE%83%E4%BB%AC%E7%9A%84%E5%92%8C%E4%B8%BA%E4%B8%80%E7%BB%99%E5%AE%9A%E6%95%B0"><span class="toc-number">1.7.2.</span> <span class="toc-text">2. 改变一组数的正负号使得它们的和为一给定数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-01-%E5%AD%97%E7%AC%A6%E6%9E%84%E6%88%90%E6%9C%80%E5%A4%9A%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="toc-number">1.7.3.</span> <span class="toc-text">3. 01 字符构成最多的字符串</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-%E6%89%BE%E9%9B%B6%E9%92%B1%E7%9A%84%E6%9C%80%E5%B0%91%E7%A1%AC%E5%B8%81%E6%95%B0"><span class="toc-number">1.7.4.</span> <span class="toc-text">4. 找零钱的最少硬币数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-%E6%89%BE%E9%9B%B6%E9%92%B1%E7%9A%84%E7%A1%AC%E5%B8%81%E6%95%B0%E7%BB%84%E5%90%88"><span class="toc-number">1.7.5.</span> <span class="toc-text">5. 找零钱的硬币数组合</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%8C%89%E5%8D%95%E8%AF%8D%E5%88%97%E8%A1%A8%E5%88%86%E5%89%B2"><span class="toc-number">1.7.6.</span> <span class="toc-text">6. 字符串按单词列表分割</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#7-%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C"><span class="toc-number">1.7.7.</span> <span class="toc-text">7. 组合总和</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93"><span class="toc-number">1.8.</span> <span class="toc-text">股票交易</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E9%9C%80%E8%A6%81%E5%86%B7%E5%8D%B4%E6%9C%9F%E7%9A%84%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93"><span class="toc-number">1.8.1.</span> <span class="toc-text">1. 需要冷却期的股票交易</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E9%9C%80%E8%A6%81%E4%BA%A4%E6%98%93%E8%B4%B9%E7%94%A8%E7%9A%84%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93"><span class="toc-number">1.8.2.</span> <span class="toc-text">2. 需要交易费用的股票交易</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-%E5%8F%AA%E8%83%BD%E8%BF%9B%E8%A1%8C%E4%B8%A4%E6%AC%A1%E7%9A%84%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93"><span class="toc-number">1.8.3.</span> <span class="toc-text">3. 只能进行两次的股票交易</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-%E5%8F%AA%E8%83%BD%E8%BF%9B%E8%A1%8C-k-%E6%AC%A1%E7%9A%84%E8%82%A1%E7%A5%A8%E4%BA%A4%E6%98%93"><span class="toc-number">1.8.4.</span> <span class="toc-text">4. 只能进行 k 次的股票交易</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%BC%96%E8%BE%91"><span class="toc-number">1.9.</span> <span class="toc-text">字符串编辑</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E5%88%A0%E9%99%A4%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%AD%97%E7%AC%A6%E4%BD%BF%E5%AE%83%E4%BB%AC%E7%9B%B8%E7%AD%89"><span class="toc-number">1.9.1.</span> <span class="toc-text">1. 删除两个字符串的字符使它们相等</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB"><span class="toc-number">1.9.2.</span> <span class="toc-text">2. 编辑距离</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-%E5%A4%8D%E5%88%B6%E7%B2%98%E8%B4%B4%E5%AD%97%E7%AC%A6"><span class="toc-number">1.9.3.</span> <span class="toc-text">3. 复制粘贴字符</span></a></li></ol></li></ol></li></ol></div></div></div></div></main><footer id="footer" style="background-image: url('/hexo3/img/12.jpg')"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2022 By Zhang Shuo</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text">Hi, welcome to my blog!</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="font-plus" type="button" title="放大字体"><i class="fas fa-plus"></i></button><button id="font-minus" type="button" title="缩小字体"><i class="fas fa-minus"></i></button><button id="translateLink" type="button" title="简繁转换">簡</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><div class="search-dialog__title" id="local-search-title">本地搜索</div><div id="local-input-panel"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div></div><hr/><div id="local-search-results"></div><span class="search-close-button"><i class="fas fa-times"></i></span></div><div id="search-mask"></div></div><div><script src="/hexo3/js/utils.js"></script><script src="/hexo3/js/main.js"></script><script src="/hexo3/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script src="https://cdn.jsdelivr.net/npm/vanilla-lazyload/dist/lazyload.iife.min.js"></script><script src="/hexo3/js/search/local-search.js"></script><script>var preloader = {
  endLoading: () => {
    document.body.style.overflow = 'auto';
    document.getElementById('loading-box').classList.add("loaded")
  },
  initLoading: () => {
    document.body.style.overflow = '';
    document.getElementById('loading-box').classList.remove("loaded")

  }
}
window.addEventListener('load',preloader.endLoading())</script><div class="js-pjax"></div><div class="aplayer no-destroy" data-id="000PeZCQ1i4XVs" data-server="tencent" data-type="artist" data-fixed="true" data-mini="true" data-listFolded="false" data-order="random" data-preload="none" data-autoplay="true" muted></div><script defer="defer" id="fluttering_ribbon" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-fluttering-ribbon.min.js"></script><script id="canvas_nest" defer="defer" color="0,0,255" opacity="0.7" zIndex="-1" count="99" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-nest.min.js"></script><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/activate-power-mode.min.js"></script><script>POWERMODE.colorful = true;
POWERMODE.shake = false;
POWERMODE.mobile = true;
document.body.addEventListener('input', POWERMODE);
</script><script id="click-heart" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/click-heart.min.js" async="async" mobile="true"></script><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script><script src="https://cdn.jsdelivr.net/gh/metowolf/MetingJS@1.2/dist/Meting.min.js"></script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.min.js"></script><script>let pjaxSelectors = [
  'title',
  '#config-diff',
  '#body-wrap',
  '#rightside-config-hide',
  '#rightside-config-show',
  '.js-pjax'
]

if (false) {
  pjaxSelectors.unshift('meta[property="og:image"]', 'meta[property="og:title"]', 'meta[property="og:url"]')
}

var pjax = new Pjax({
  elements: 'a:not([target="_blank"])',
  selectors: pjaxSelectors,
  cacheBust: false,
  analytics: false,
  scrollRestoration: false
})

document.addEventListener('pjax:send', function () {

  // removeEventListener scroll 
  window.removeEventListener('scroll', window.tocScrollFn)
  window.removeEventListener('scroll', scrollCollect)

  typeof preloader === 'object' && preloader.initLoading()
  
  if (window.aplayers) {
    for (let i = 0; i < window.aplayers.length; i++) {
      if (!window.aplayers[i].options.fixed) {
        window.aplayers[i].destroy()
      }
    }
  }

  typeof typed === 'object' && typed.destroy()

  //reset readmode
  const $bodyClassList = document.body.classList
  $bodyClassList.contains('read-mode') && $bodyClassList.remove('read-mode')

})

document.addEventListener('pjax:complete', function () {
  window.refreshFn()

  document.querySelectorAll('script[data-pjax]').forEach(item => {
    const newScript = document.createElement('script')
    const content = item.text || item.textContent || item.innerHTML || ""
    Array.from(item.attributes).forEach(attr => newScript.setAttribute(attr.name, attr.value))
    newScript.appendChild(document.createTextNode(content))
    item.parentNode.replaceChild(newScript, item)
  })

  GLOBAL_CONFIG.islazyload && window.lazyLoadInstance.update()

  typeof chatBtnFn === 'function' && chatBtnFn()
  typeof panguInit === 'function' && panguInit()

  // google analytics
  typeof gtag === 'function' && gtag('config', '', {'page_path': window.location.pathname});

  // baidu analytics
  typeof _hmt === 'object' && _hmt.push(['_trackPageview',window.location.pathname]);

  typeof loadMeting === 'function' && document.getElementsByClassName('aplayer').length && loadMeting()

  // Analytics
  if (false) {
    MtaH5.pgv()
  }

  // prismjs
  typeof Prism === 'object' && Prism.highlightAll()

  typeof preloader === 'object' && preloader.endLoading()
})

document.addEventListener('pjax:error', (e) => {
  if (e.request.status === 404) {
    pjax.loadUrl('/404.html')
  }
})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>